#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
//粉刷房子：https://leetcode.cn/problems/JEj789/description/
using namespace std;
class Solution {
public:
    //nums[i][j]: 第i个房子,j有三个值，分别对应红，蓝，绿
    //1.状态表示：
    //         f[i]: i号房子刷红色的最小花费
    //         g[i]: i号房子刷蓝色的最小花费
    //         h[i]: i号房子刷绿色的最小花费
    //2.状态转移方程：s[i]=nums[i][x]+min(另外的状态)
    //3.填表顺序：从左往右
    //4.返回值： 三种状态的最小者
    int minCost(vector<vector<int>>& costs) {
        int n=costs.size();
        vector<int> f(n);
        auto g=f;
        auto h=f;
        f[0]=costs[0][0],g[0]=costs[0][1],h[0]=costs[0][2];
        for(int i=1;i<n;i++)
        {
            f[i]=costs[i][0]+min(g[i-1],h[i-1]);
            g[i]=costs[i][1]+min(f[i-1],h[i-1]);
            h[i]=costs[i][2]+min(f[i-1],g[i-1]);
        }
        int tmp1=f[n-1];
        int tmp2=min(g[n-1],h[n-1]);
        return tmp1>tmp2?tmp2:tmp1;
    }
};